#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 2005;
int _, n, m, Dis[MAXN], Tag[MAXN]; vector<int> To[MAXN];
int BFS(int s){
  fill_n(Tag, n + 1, 0); queue<int> Q; Q.push(s), Dis[s] = 0;
  while(!Q.empty()){
    int id = Q.front(); Q.pop();
    for(int nxt: To[id]) if(!Tag[nxt] && nxt != s) Q.push(nxt), Tag[nxt] = Tag[id]? Tag[id]: nxt, Dis[nxt] = Dis[id] + 1;
    else if(Tag[id] && Tag[nxt] && Tag[id] != Tag[nxt]) return Dis[id] + Dis[nxt];
  }
  return n;
}
int query(){
  int res = n;
  for(int i = 1; i <= n; i++) res = min(res, BFS(i));
  return res;
}
template <uint32_t mod> class mod_int{
  private:
    static constexpr uint32_t get_r(){
      uint32_t ret = mod;
      for(int i = 0; i < 4; i++) ret *= 2 - mod * ret;
      return ret;
    }
    static constexpr uint32_t r = get_r();
    static constexpr uint32_t n2 = -uint64_t(mod) % mod;
    static_assert(r * mod == 1 && mod < (1 << 30) && mod & 1);
    uint32_t data;
  public:
    constexpr mod_int(): data(0){}
    template <class int_t> constexpr mod_int(const int_t x): data(reduce(uint64_t((sizeof(int_t) < sizeof(uint32_t)? x: x % int_t(mod)) + mod) * n2)){};
    static constexpr uint32_t reduce(const uint64_t x){return (x + uint64_t(uint32_t(x) * (-r)) * mod) >> 32;}
    constexpr mod_int& operator += (const mod_int &r){if(int32_t(data += r.data - 2 * mod) < 0){data += 2 * mod;} return *this;}
    constexpr mod_int& operator -= (const mod_int &r){if(int32_t(data -= r.data) < 0){data += 2 * mod;} return *this;}
    constexpr mod_int& operator *= (const mod_int &r){return data = reduce((uint64_t)data * r.data), *this;}
    constexpr mod_int& operator /= (const mod_int &r){return *this *= r.inv();}
    constexpr friend mod_int operator + (mod_int l, const mod_int &r){return l += r;}
    constexpr friend mod_int operator - (mod_int l, const mod_int &r){return l -= r;}
    constexpr friend mod_int operator * (mod_int l, const mod_int &r){return l *= r;}
    constexpr friend mod_int operator / (mod_int l, const mod_int &r){return l /= r;}
    constexpr mod_int operator - () const {return mod_int() - mod_int(*this);}
    template <class int_t> constexpr mod_int pow(int_t r) const {mod_int res(1), w(*this); for(; r; r >>= 1, w *= w) if(r & 1) res *= w; return res;}
    constexpr mod_int inv() const {return pow(mod - 2);}
    constexpr uint32_t value() const {uint32_t res = reduce(data); return res >= mod? res - mod: res;}
}; typedef mod_int<998244353> mint;
mint Fac(int n){
  mint res = 1;
  for(int i = 1; i <= n; i++) res *= i;
  return res;
}
mint C(int x, int y){
  return Fac(x) / (Fac(y) * Fac(x - y));
}
int main(){
  freopen("oi.in", "r", stdin);
  freopen("oi.out", "w", stdout);
  cin.tie(nullptr)->sync_with_stdio(false);
  for(cin >> _ >> _; _--;){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) To[i].clear();
    for(int i = 1; i <= m; i++){int x, y; cin >> x >> y, To[x].push_back(y), To[y].push_back(x);}
    cout << 1 - query() - m << ' ' << (C(3 * (n - 1), n - 1) / (2 * (n - 1) + 1)).value() << '\n';
  }
  return 0;
}
